package com.example;

import java.util.*;

/**
 * @Author loubobooo
 * @Description #94. 二叉树的中序遍历
 * @Date 2020/1/2
 */
public class BinaryTreeInorderTraversal {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private List<Integer> list = new LinkedList<>();

    /**
     * @return
     * @Author loubobooo
     * @Description 给定一个二叉树，返回它的中序遍历。
     * 示例:
     * 输入: [1,null,2,3]
     * 1
     * \
     * 2
     * /
     * 3
     * 输出: [1,3,2]
     * @Date 2020/1/2 15:56
     * @Param
     **/
    public List<Integer> inorderTraversal(TreeNode root) {
        //中序遍历以node为根的二分搜索树，递归算法
        // 先访问该节点的左子树，再访问该节点，最后访问该节点的右子树
        inOrder(root);
        return list;
    }

    private void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        list.add(node.val);
        inOrder(node.right);
    }


}
